package toOffer;

import java.util.*;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/2/2 8:31
 * @description <p>插入、删除和随机访问都是 O(1)的容器 </p>
 */
public class toOffer5_2_30 {
    public static void main(String[] args) {

    }

    private static Map<Integer, Integer> map;
    private static List<Integer> list;

    /**
     * Initialize your data structure here.
     */
    public toOffer5_2_30() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    /**
     * 插入
     *
     * @param val
     * @return
     */
    public boolean insert(int val) {
        //判断val在数组中是否存在，已经存在就不能再添加了
        if (map.containsKey(val)) {
            return false;
        }

        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    /**
     * list删除数据不能直接把该数字删除。这是因为待删除的数字不一定位于数组的尾部。
     * 当数组中间的数字被删除之后，为了确保数组内存的连续性，
     * 被删除的数字后面的数字会向前移动以填补被删除的内容空缺。
     *
     * @param val
     * @return
     */
    public boolean remove(int val) {
        //判断val是否存在，不存在就不能删除
        if (!map.containsKey(val)) {
            return false;
        }

        //获取val在list里的下标
        Integer index = map.get(val);
        //把list里的val用list的最后一个数据表示
        int lastNum = list.get(list.size() - 1);
        list.set(index, lastNum);
        //删除list里的最后一个数据
        list.remove(list.size() - 1);
        //更新map里lastNum的value
        map.put(lastNum, index);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        Random random = new Random();
        int rd = random.nextInt(list.size());
        return list.get(rd);
    }
}